/**
* @description: 779. 第K个语法符号
* @author hewei
* @date 2022/8/27 14:11
* @version 1.0
*/

public class KthGrammar {

    public int kthGrammar(int n, int k) {
        int ans = 0;
        for (int i = n; i > 1; i--) {
            if (k % 2 == 0) {
                ++ans;
            }
            k = (k + 1) / 2;
        }
        return ans % 2 == 0 ? 0 : 1;
    }
}
